This invention relates to a method and apparatus for compressing and/or decompressing data in a memory of a computer system. In particular, this invention relates to a method and apparatus for compressing uncompressed data in a first level memory of a computer system for storage in a second level memory of the computer system, and/or for decompressing compressed data in a second level memory of a computer system for storage in a first level memory of the computer system
It is known to use data compression schemes to compress data held in the memory of a computer system. These schemes increase the effective capacity of the memory.
Computer systems often employ a hierarchical arrangement of memory levels in which smaller capacity but faster memory is located closer to a processor, whereas larger capacity but slower memory is provided at lower, more distant levels. For example, one such arrangement includes three memory levels in order of decreasing distance from the processor: storage (e.g., a hard disk), main memory (e.g., RAM) and cache memory. Additional cache memory levels can also be included. For example, in a two-level cache arrangement, a so-called L1 cache can be provided in between a processor and an L2 cache. Such an arrangement would include four memory levels in total. Where the processor registers are considered as a level of memory, then there would be five memory levels in this example.
In a hierarchical memory, data compression can be used between two levels of memory, to increase the effective capacity of the memory level which is more distant from the processor.
Compression can be used between memory levels, for example between a cache and a main memory. When data is written to the memory level which is more distant from the processor (also known as the lower memory level), a data compression scheme can be applied such that the data is stored in the more distant memory element in compressed form. Conversely, when data is read from the lower memory level in compressed form, the data compression scheme can be applied (hereinafter referred to as the data decompression scheme, although it will be understood that the data decompression scheme is normally just the reverse application of the data compression scheme) to decompress the data for entry into a higher memory level, which is less distant from the processor.
Memory in computer systems is normally arranged in a plurality of words. For example, a cache can comprise a plurality of cache lines, or cache blocks. Each cache line, or cache block, can typically store one or more data words. In many memory protocols, data is retrieved and written into a cache memory on a block-by-block basis. Similar considerations apply to main memory and storage. When a data compression scheme is applied, it can be applied on a block-by-block and/or word-by-word basis.
An example of a data compression scheme which is used in this context is the Frequent Pattern Compression (FPC) scheme. An overview of this scheme is described in a paper entitled “Frequent Pattern Compression: A Significance-Based Compression Scheme for L2 Caches”, by Alaa R. Alameldeen and David A. Wood, Technical Report 1500, Computer Sciences Dept., UW-Madison, April 2004. This paper is available at www.cs.wisc.edu/multifacet/papers/tr1500_frequent_pattern_compression.pdf. Some examples of the FPC scheme are described below.